The present invention relates to a packet relaying apparatus for relaying a packet in a plurality of interconnected networks, and more particularly to a method of searching a next node to which a multicast packet is transmitted.
As the number of users of the Internet increases and the traffic (packets) on the Internet rapidly increases, the scale and speed of the Internet are becoming large and high. In the current Internet (packet communication network by Internet Protocol: hereinafter called an IP network), not only conventional data communication applications, but also real time applications such as Internet phones and Internet broadcasting are used to provide a voice communication function and a broadcasting function. Under such circumstances, IP multicast techniques for the IP network are expected as effective techniques for the distribution of multimedia data such as moving images, voices and contents on the Internet.
Support and high speed operation of a packet relaying apparatus (router) constituting the IP network are the main issue of IP multicast techniques.
In unicast communication for transmitting a packet from one terminal to another specific terminal, a router searches from a routing table, route information corresponding to a receiver IP address contained in a header of a received packet, and transmits the received packet to the next router. The route information includes an IP address of the next router or a terminal and a transmission port number of the router. A route search for unicast will be briefly described.
The routing table stores a plurality of information groups for each receiver IP address, the information groups including a corresponding sub-network address, a sub-net mask length, and the route information. This information group is called an entry. The sub-network is a partial collection of terminals such as a receiver corporate network. The sub-network address is an address group which is obtained by coupling IP addresses of the partial collection as address information. The sub-net mask length is a value indicating how many upper bits of an IP address are an identifier of the sub-network. The router compares the sub-network address in the entry with the effective upper bits, masked by the sub-net mask length in the entry, of a receiver IP address contained in a received packet. The router-uses the route information in the coincident entry as the search result. Since the entry is configured in the unit of sub-network, the number of entries in the routing table can be reduced considerably and the search process is made efficient. If it is judged that a plurality of entries are coincident, the route information in the entry having the longest sub-net mask length is used as the search result. In the following, this search is called a longest coincidence search.
In multicast communication for transmitting a packet from one terminal to a plurality of specific terminals, each entry of the routing table includes a sender sub-net address, an address mask, a multicast group address and route information. The multicast group address is an identifier assigned to a plurality of receiver collections (hereinafter called a multicast group) to which the sender transmits the packet. A router searches the routing table by using as a search key a multicast group address in the sender IP address and receiver IP addresses in the header field of a received packet. In multicast, the route information of an entry with a search coincidence is constituted of a plurality of transmission port numbers. In accordance with the transmission port numbers, the router copies the received packet and transmits it to the specific multicast group. If the load of the search process and copy process is heavy and the performance of multicast communication is low, the total performance of the router which executes a multicast packet transfer may be degraded. From this reason, a high speed operation is required similar to a usual unicast packet relaying process.
A high speed operation to be attained through a router load dispersion method is described, for example, in JP-A-6-197111 laid-open on Jul. 15, 1994 (hereinafter called xe2x80x9cfirst related artxe2x80x9d). This first related art aims to realize a router capable of a high speed relay operation through a load dispersion method. A plurality of packet relay modules are connected to a bus, and each packet relay module provides a packet relay function by referring to routing table information supplied from a management unit connected to the bus. If the number of packet relay modules is increased, the performance can be improved. The packet relay module of the first related art includes: a routing processing unit which derives the header of a received packet and performs a search process for a packet receiver; and a transfer processing unit which stores the received packet in a memory and transfers the received packet to another packet relay module designated by the search result. Since the different processing units take partial charge of the relay function, the packet relay process can be speeded up. However, the first related art does not describe a high speed multicast packet relay process.
A search (hereinafter called a multicast route search) of a receiver of a multicast packet to be performed by a router is described, for example, in xe2x80x9cTCP/IP Illustrated, Volume 2 The Implementationxe2x80x9d, 1995, pp. 416-421 (Addison-Wesley Publishing Company) (hereinafter called a second related art). According to the second related art, the routing table search is speeded up by using a hash search method. If the routing table information is directly searched, the time taken to execute a search process becomes considerably long as the number of receiver IP addresses increases and the number of entries of the table increases. According to the second related art, a sender ID address in a received packet is used as a key for calculating a hash value, and a routing table group is provided which stores grouped entries of the receiver IP addresses having the same hash value.
When a multicast packet is received, the route search processing unit in the router calculates the hash value from the sender IP address in the received packet and the routing table corresponding to the hash value is searched. Since the search range of the routing table is limited in accordance with the hash value, the route search can be speeded up.
A Radish algorithm is known as one of route searching methods. The Radish algorithm is described, for example, in xe2x80x9cA technical memo of WIDE project, Kazukio Yamamoto, Akira Kato and Akira Watanabe, Radish-A Simple Table Structure for CIDR (hereinafter called a third related art).
A routing table of the Radish type uses entries of a two-branch tree structure to speed up the route search. More specifically, each entry is allocated to each of a plurality of apexes (nodes) interconnected by right and left pointers of each node constituting a two-branch tree structure wherein the root (two-branch tree root) corresponds to the highest bit of an IP address format. When this two-branch tree structure is searched, the receiver IP address in a received packet is checked one bit after another starting from the highest bit, and one of right and left pointers is selected in accordance with the checked bit value (0 or 1) to move to the next node. With this search, the node assigned the target entry can be reached.
According to the third related art, the two-branch tree is traced by checking the receiver IP address one bit after another. Therefore, even if the number of entries of the routing table becomes large, the search can be completed by performing a check (tracing the two-branch tree) as many as the number of bits of the receiver IP address at the maximum.
Similar to the case wherein there are a plurality of matched entries having different mask lengths as described in the route search for unicast, there are also a plurality of matched entries while the tree is traced by searching the routing table of the Radish type of the third related area. Each time an entry is matched, a candidate for the route information in the entry is stored, and if a new entry is matched, the previous candidate is updated to the new candidate to satisfy the longest coincidence search specification.
Techniques of performing a unicast route search at high speed by using the Radish method of the third related art is disclosed in the paper xe2x80x9cHigh Speed Search Method for IP Routing Table by Hardwarexe2x80x9d, PROCEEDINGS OF THE 1998 COMMUNICATIONS SOCIETY CONFERENCE of the Institute of Electronics, Information and Communication Engineers (IEICE), B-7-123, p. 244 (hereinafter called a fourth related art). According to the fourth related art, a next node selector circuit, a network address comparator circuit and a search completion judging circuit are provided. The network address comparator circuit is used for checking at the same time one or a plurality of consecutive bits to be checked at a branch omitted as unnecessary from the two-branch tree of the Radish type, by comparing a network address at the node and the receiver IP address in a received packet masked by the node. If the comparison result indicates a coincidence, it means that a correct node was reached, whereas if incoincidence, it means that an incorrect node was reached.
According to the fourth related art, a next node selection process and the network address comparison process are executed in parallel to speed up the route search process.
Techniques of performing a unicast route search at high speed by using a Patricia Trie search algorithm similar to the Radish type are described in xe2x80x9cDevelopment of High Speed IP Address Solution H/W Enginexe2x80x9d, PROCEEDINGS OF THE 1998 COMMUNICATION SOCIETY CONFERENCE OF IEICE, B-6-90, p. 90 (hereinafter called a fifth related art). Similar to the fourth related art, the fifth related area speeds up the route search by executing tree structure searching processes in parallel.
Techniques of further speeding up the unicast route search by using a Patricia Trie search algorithm is described in xe2x80x9cHigh Speed Search Method for IP Routing Table by Multi-way Treexe2x80x9d, PROCEEDINGS OF THE 1998 COMMUNICATIONS SOCIETY CONFERENCE OF IEICE, B-7-124, p. 245 (hereinafter called a sixth related art). According to the sixth related art, the two-branch tree structure using the Patricia Trie algorithm is changed to the N-th power-of-2-branch tree in order to speed up the route search.
Techniques of speeding up the unicast route search with the longest coincidence search is described in JP-A-10-222535 laid-open on Aug. 21, 1998 (hereinafter called a seventh related art). According to the seventh related art, the two-branch tree is structured by a method different from the Radish type of the third related art. By using a data search circuit made of hardware, the longest coincidence search for the two-branch tree is performed at high speed. More specifically, with the two-branch tree searching method of the seventh related art, the receiver IP address in a received packet which is sub-net masked by the node is compared with the sub-network address of the node. If the comparison result indicates a coincidence, the route information of this node is used as the search result to terminate the route search, where as if incoincidence, the masked receiver address and the sub-network address of the node are assumed to be an integer not smaller than 0, and both the addresses are compared to trace one of right and left branches of the two-branch tree in accordance with the comparison result. In this case, if entries having the longer mask length are disposed at the upper level of the two-branch tree, the search is performed in the order of longer mask length so that the longest coincidence search can be realized. The contents of the seventh related art have been described above on the assumption that the mask length is defined as a value indicating what upper bits are valid as the sub-network address. However, in the specification of the seventh related art, the mask length is defined as a length of lower bits different from the sub-network address portion of the IP address. Also, the longest coincidence search method is called a best match method. This best match method adopts the shortest mask length as the search result.
The present IP multicast communication is only used limitatively in the multicast network virtually configured on the Internet. The scale of the multicast network is not so large and the search process and transfer process of multicast communication do not degrade the transfer performance of a rooter as yet. However, if applications using the multicast function are prevailed on the Internet in the future, the number of entries of the multicast routing table in a rooter becomes large. Therefore, it is desired to realize a high speed operation of a search process for the routing table even under the conditions of a large number of entries.
The multicast route searching method of the hash type is described in the second related art. With the hash type, however, the method of calculating a hash value is always the same irrespective of the number of entries. It is not possible to flexibly increase the number of routing table groups in accordance with an increase in the number of entries. Therefore, if the number of entries increases, the grouped routing table itself becomes large and an average search time becomes long.
As compared to the hash type, the unicast route searching method using the Radish algorithm has a merit that even if the number of entries in the routing table increases, the search process time does not become long.
However, the third and fifth related arts do not describe a multicast route search using the Radish algorithm (or Patricia Trie algorithm).
Although the sixth related art describes the maximum search time shortened by 1/N by changing the two-branch tree structure to N-th power-of-2-branch trees, it does not describe the multicast route search.
Neither the seventh related art describes a high speed operation of the multicast route search. The two-branch tree structure of the third related art is determined uniquely by the entries to be registered and its maximum search time is determined by the number of bits of a search key. In contrast, the two-branch tree, structure of the seventh related art may have in some cases a tree having nodes coupled long in one direction and a long average search time, depending upon a tree configuring method. In order to avoid such a tree having a long train of nodes, it is necessary to use an algorithm which makes the two-branch tree broaden uniformly. The seventh related art, however, does not describe such an algorithm. The seventh related art describes that when the two-branch tree of the seventh related area is configured, if entries having the longer mask length are disposed at the upper level of the two-branch tree, the search is performed in the order of longer mask length so that the longest coincidence search can be realized. However, the details of coupling nodes having different mask length are not given. Furthermore, as different from the third related art in which right and left branches of a two-branch tree are not traced in accordance with the check bit value, the seventh related art traces the right and left branches of the two-branch tree in accordance with the comparison result of addresses. Therefore, a p-th power-of-2-branch system cannot be realized.
It is an object of the invention to provide means for speeding up a multicast packet route search process during the relay process for a multicast packet.
It is another object of the invention to provide means for applying a two-branch tree searching method using a Radish algorithm to a multicast route search.
It is another object of the invention to provide means for applying, to a multicast route searching method, a route searching method which provides the number of node tracing times smaller than the large number of bits of a search key and a short maximum search time.
It is another object of the invention to provide a circuit structure capable of performing a route search process at high speed in accordance with a two-branch tree searching method for a multicast routing table by using a Radish algorithm.
According to one aspect of the present invention, in a multicast route search using as a search key a packet sender terminal IP address (sender IP address) and a packet receiver multicast group address (receiver multicast group address), the sender ID address and receiver multicast group address are coupled to form and define one route address. In accordance with a bit pattern of this route address, a multicast routing table of a two-branch tree is configured. Each bit starting from an upper bit of the route address coupling the sender ID address and receiver multicast group address in a received multicast packet is checked, and in accordance with a value of the checked bit, a search tree of a two-branch tree structure is searched.
According to another aspect of the present invention, the route address is defined by coupling the receiver multicast group address and sender ID address in this order, and in accordance with a bit pattern of this route address, the multicast routing table of the two-branch tree is configured.
According to another aspect of the present invention, the number of branches of each node constituting a search tree of the two-branch tree is increased by a power of 2, from a two-branch tree node to a four-branch tree node, an eight-branch tree node, or generally a p-th power-of-2-branch tree to configure a multicast routing table of the p-th power-of-2-branch tree structure. Not one bit per one node, but consecutive two bits, three bits, or generally p bits of the route address coupling the receiver multicast group address and sender IP address in a received multicast packet in this order are checked at the same time. In accordance with the values of the consecutive bits, the multicast routing table of the p-th power-of-2-branch is searched.
According to another aspect of the present invention, as the route address, the multicast group address itself is not used but the multicast group ID of the lower 28 bits of the multicast group address and the sender IP address coupled in this order are used. In accordance with the bit pattern of this route address, the multicast routing table is configured as a two-branch tree or a p-th power-of-2-branch tree.
According to another aspect of the present invention, in order to reduce the memory capacity of a search key, when a p-th power-of-2-branch tree is formed, a collection of one two-branch tree node and two-branch tree nodes of (pxe2x88x921) stages, totalling in ((a p-th power of 2)xe2x88x921) nodes just under the one upper node, is used as one p-th power-of-2-branch tree node. In this case, the (pxe2x88x921)-th power of 2) two-branch nodes at the lowest stage collected are embedded with the entry data assigned to the nodes at the higher stages to form one p-th power-of-2-branch tree node by using ((pxe2x88x921)-th power of 2) two-branch nodes. In this case, one element of node data common to a plurality of two-branch tree is stored.
According to another aspect of the present invention, in converting two-branch tree nodes into a p-th power-of-2-branch tree, in order to reduce the memory capacity for the p-th power-of-2-branch tree node and to made equal the memory amount of each p-th power-of-2-branch tree node, the transmission port information is separated from the node data of the search tree and stored in another area of a memory. As a result, the data amount of the two-branch tree node assigned an entry becomes equal to the data amount of the two-branch tree node not assigned an entry, to thereby configure a p-th power-of-2-branch tree nodes by collecting such two-branch tree nodes.
According to another aspect of the present invention, as to the mask length indicating the position of a bit of the route address to be checked, the mask length of each p-th power-of-2-branch tree node is not stored but the mask length of another node just under the p-th power-of-2-branch tree node is stored. In this case, all the data of the node is not read from storage means storing the search tree data to be used for a route search process, but only the necessary portion of the node data is read by using the mask length stored in the node data which was read immediately before.
According to another aspect of the present invention, at the start of the node data, a flag indicating whether an entry is assigned to the node is provided. This flag is first read, and if the entry is not assigned, the route information of this node is not read.
According to another aspect of the present invention, (m-power of 2) p-th power-of-2-branch tree nodes corresponding in number to the upper m bits of the route address are developed on the storage means at predetermined positions. Each of the developed nodes is being set in one-to-one correspondence with each value which the 0-th bit to (mxe2x88x921)-th bit of the route address can take. In accordance with the 0-th bit to (mxe2x88x921)-th bit of the route address, one of the developed nodes is selected.
According to another aspect of the present invention, there is provided a circuit for searching a multicast routing table of a p-th power-of-2-branch tree structure in which: a route address is formed by coupling a receiver address and a sender address in this order; storing means is provided for storing by developing (m-th power of 2) p-th power-of-2-branch tree nodes of a p-th power-of-2-branch tree structure corresponding to the upper m bits of the route address, at predetermined positions; one of the developed nodes in the storage means at predetermined positions is selected in accordance with the 0-th bit to (mxe2x88x921)-th bit of the route address coupling the receiver address and sender address; and every p bits of the route address after the m-th bit of the route address are checked.
Other objects and features of the present invention will become apparent from the following description when read in conjunction with the accompanying drawing.